﻿#define _CRT_SECURE_NO_WARNINGS 1

#include <iostream>
#include <vector>`

using namespace  std;


//希尔排序法⼜称缩⼩增量法。希尔排序法的基本思想是：先选定⼀个整数（通常是gap = n / 3 + 1），把
//待排序⽂件所有记录分成各组，所有的距离相等的记录分在同⼀组内，并对每⼀组内的记录进⾏排
//序，然后gap = gap / 3 + 1得到下⼀个整数，再将数组分成各组，进⾏插⼊排序，当gap = 1时，就相当于
//直接插⼊排序。

// 希尔排序
//void shellSort(vector<int>& arr) {
//    int n = arr.size();
//
//    // 初始间隔设为n/2，逐渐减小间隔
//    for (int gap = n / 2; gap > 0; gap /= 2) {
//        // 对每个间隔组进行插入排序
//        for (int i = gap; i < n; i++) {
//            int temp = arr[i];
//            int j;
//
//            // 移动同组中比temp大的元素
//            for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
//                arr[j] = arr[j - gap];
//            }
//            arr[j] = temp;
//        }
//    }
//}

void shellSort(int* a, int n)
{
	//int gap = n;
	//while (gap > 1)
	//{
	//	//推荐写法：除3
	//	gap = gap / 3 + 1;
	//	for (int i = 0; i < n - gap; i++)
	//	{
	//		int end = i;
	//		int tmp = a[end + gap];
	//		while (end >= 0)
	//		{
	//			if (a[end] > tmp)
	//			{
	//				a[end + gap] = a[end];
	//				end -= gap;
	//			}
	//			else
	//			{
	//				break;
	//			}
	//		}
	//		a[end + gap] = tmp;
	//	}
	//}

	int gap = n;
	int end = 0;
	while (gap > 1)
	{
		gap = gap / 3 + 1;
		for (int i = 0; i < n - gap; i++) {
			end = i;
			int temp = a[end + gap];

			while (end >= 0 && a[end] > temp)
			{
				a[end + gap] = a[end];
				end -= gap;
			}
			a[end + gap] = temp;
		}
		
	}
}

int main()
{
	int  array[5] = { 3,2,4,1,5 };
	int  n = 5;
	shellSort(array, n);
	for (int i = 0; i < n; i++)
	{
		printf("%d ", array[i]);
	}
	return 0;
}



